package doublePointer;

import org.junit.Test;

import java.util.Stack;

/**
 * @author kunkun
 * @className LeetCode_283
 * @Description 给定一个数组 nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。
 * @date 2025/2/27 16:53
 */
public class LeetCode_283 {

    public void moveZeroes(int[] nums) {
        solution_2(nums);
    }

    @Test
    public void test_solution1(){
        int[] nums = {4,2,4,0,0,3,0,5,1,0};
//        int[] nums = {0};
        moveZeroes(nums);
        for (int num : nums) {
            System.out.print(num+" ");
        }
    }

    /**
    * @Description: 方法1：利用栈处理（空间复杂度O（n））
    * @Author: kunkun
    * @Date:  2025/2/27 16:56
    * @Parameters:
    * @Return
    * @Throws
    */
    public static void solution_1(int[] nums){
        //1. 集体入栈，同时对0计数，删除0
        Stack<Integer> stack = new Stack<>();
        int count = 0;
        for (int num : nums) {
            if (num!=0){
                stack.push(num);
            }else{
                count++;
            }
        }
        //2. 将栈中元素入队
        for (int i = nums.length-count-1; i >= 0; i--) {
            nums[i]=stack.pop();
        }
        for (int i = nums.length-count; i < nums.length; i++){
            nums[i]=0;
        }

    }

    /**
    * @Description: 方法2：利用双指针处理（空间复杂度O（1）），start：当前位置，end：start的后续第一个非0位置
    * @Author: kunkun
    * @Date:  2025/2/28 10:17
    * @Parameters:
    * @Return
    * @Throws
    */
    public static void solution_2(int[] nums){
        //1. 排除其它情况
        if (nums.length==1){
            return;
        }
        //2. 定义start和end指针，end指向下一个非0元素
        int start=0,end=findIndex(nums,start);
        //3. 开始遍历数组
        while(end<nums.length){

            //3.1 对start位置的元素判断
            if (nums[start]==0){        //非0
                nums[start]=nums[end];
                nums[end]=0;
                start++;
                end=findIndex(nums,end);
            }else{
                start++;
                if (start>=end){
                    end=findIndex(nums,start);
                }

            }

        }
    }

    /**
     * nums中寻找start后的非0元素，没有的话返回nums.length
     * @return
     */
    public static int findIndex(int[] nums,int start){
        for (int i = start+1; i < nums.length; i++) {
            if (nums[i]!=0){
                return i;
            }
        }
        return nums.length;
    }


}
